package com.javabase.study.ArrayStudy;

import java.util.Arrays;

/**
 * TODO
 * 内容：测试学习 冒泡排序优化算法
 * 1. 整个数列份成两部分，前面是无序，后面是有序
 * 2. 初始状态下，整个数列都是无序的，有序数列是空
 * 3. 每一趟循环可以让无序数列中最大数拍到最后，即有序数增加1，也就不用去估计有序数列
 * 4. 每一趟循环都从数列的第一个元素开始进行比基奥，一次比较的两个元素，比较到
 * 无序部分的末尾即可；如果前一个元素大于后一个，交换位置
 * 5. 判断每一趟是否发生了数组元素的交换，如果没有发生，则说明此时数组已经有序，无序再
 * 进行后续趟数的比较，即中止循环
 * 作者:jxx
 * 创建时间：2021/6/23
 */
public class TestBubbleSortOptim {
    public static void main(String[] args){

        int[] a = {1,8,4,9,6,0};

        TestBubbleSortOptim testBubbleSortOptim = new TestBubbleSortOptim();
        testBubbleSortOptim.bubbleSortOptimization(a);

    }

    public static void bubbleSortOptimization(int[] src){

        int tmp;
        int srcLength = src.length;

        // 外层循环：n个元素排序，则之多需要n - 1趟循环
        for (int i = 0; i < srcLength - 1; i++){
            // 定义一个布尔类型变量，标记数组是否达到有序状态
            boolean flag = true;
            //内层循环：每一趟循环都从数列的前两个元素开始进行比较，比较无序数组到最后
            for(int j = 0 ; j < srcLength - i - 1; j++){
                // 如果前一个元素大于后一个元素，则交换两元素的值
                if(src[j] > src[j + 1]){
                    tmp = src[j];
                    src[j] = src[j + 1];
                    src[j + 1] = tmp;

                    //本趟发生了交换表命该数组在本趟处于无序状态，需要继续比较
                    flag = false;
                }
                System.out.println(Arrays.toString(src));
            }
            System.out.println("#######");
            // 根据标记量的值判断数组是否有序，如果有序，则推出；无序，则继续循环
            if(flag){
                break;
            }
        }

    }
}
